#include <vector>
#include <string>

using namespace std;

// 贴纸拼词
// 我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。
// 您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们
// 如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。
// 返回你需要拼出 target 的最小贴纸数量。如果任务不可能，则返回 -1
// 注意：在所有的测试用例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选择的
// 并且 target 被选择为两个随机单词的连接。
// 测试链接 : https://leetcode.cn/problems/stickers-to-spell-word/

class Solution 
{
private:
    static const int MAXN = 401;
    string q[MAXN];
    int l, r;


    // 用 s 中的字符抵消 t 中的字符
    string nextStr(string& t, string& s)
    {
        string ret;
        for(int i = 0, j = 0; i < t.size();)
        {
            // 来到了 s 的末尾，则 t 中剩余的字符都是无法抵消的
            if(j == s.size())
                ret += t[i++];
            else
            {
                if(t[i] < s[j])
                    ret += t[i++]; // 无法抵消的字符需要添加到答案中
                else if(t[i] > s[j])
                    ++j;
                else
                    ++i, ++j; // 字符相等，进行抵消
            }
        }
        return ret;
    }

public:
	// 宽度优先遍历的解法
	// 也可以使用动态规划
    int minStickers(vector<string>& stickers, string target) 
    {
        // 建图
        // 下标 0 -> a
        // 下标 1 -> b
        // 下标 2 -> c
        // ...
        // 下标 25 -> z
        vector<vector<string>> g(26);
        for(auto& str : stickers)
        {
            sort(str.begin(), str.end());
            for(int i = 0; i < str.size(); ++i)
            {
                if(i == 0 || str[i] != str[i - 1])
                {
                    g[str[i] - 'a'].emplace_back(str);
                }
            }
        }

        sort(target.begin(), target.end());
        unordered_set<string> visited;
        visited.insert(target);
        l = r = 0;
        q[r++] = target;
        int level = 1;
        while(l < r)
        {
            int size = r - l;
            // 使用队列的形式是整层弹出
            while(size--)
            {
                string& cur = q[l++]; 
                // 先把 cur 的第一个字符先抵消掉
                for(auto& s : g[cur[0] - 'a'])
                {
                    string next = nextStr(cur, s);
                    // target 中的字符全部抵消掉了
                    if(next.empty()) return level;
                    else if(!visited.count(next))
                    {
                        visited.insert(next);
                        q[r++] = next;
                    }
                }
            }
            ++level;
        }
        return -1;
    }
};

class Solution 
{
private:
    // 用 s 中的字符抵消 t 中的字符
    string nextStr(string& t, string& s)
    {
        string ret;
        for(int i = 0, j = 0; i < t.size();)
        {
            // 来到了 s 的末尾，则 t 中剩余的字符都是无法抵消的
            if(j == s.size())
                ret += t[i++];
            else
            {
                if(t[i] < s[j])
                    ret += t[i++]; // 无法抵消的字符需要添加到答案中
                else if(t[i] > s[j])
                    ++j;
                else
                    ++i, ++j; // 字符相等，进行抵消
            }
        }
        return ret;
    }

public:
	// 宽度优先遍历的解法
	// 也可以使用动态规划
    int minStickers(vector<string>& stickers, string target) 
    {
        // 建图
        // 下标 0 -> a
        // 下标 1 -> b
        // 下标 2 -> c
        // ...
        // 下标 25 -> z
        vector<vector<string>> g(26);
        for(auto& str : stickers)
        {
            sort(str.begin(), str.end());
            for(int i = 0; i < str.size(); ++i)
            {
                if(i == 0 || str[i] != str[i - 1])
                {
                    g[str[i] - 'a'].push_back(str);
                }
            }
        }

        sort(target.begin(), target.end());
        unordered_set<string> visited;
        visited.insert(target);
        queue<string> q;
        q.push(target);
        int level = 1;
        while(!q.empty())
        {
            int m = q.size();
            while(m--)
            {
                string cur = q.front();
                q.pop();
                // 先把 cur 的第一个字符先抵消掉
                for(auto& s : g[cur[0] - 'a'])
                {
                    string next = nextStr(cur, s);
                    // target 中的字符全部抵消掉了
                    if(next.empty()) return level;
                    else if(!visited.count(next))
                    {
                        visited.insert(next);
                        q.push(next);
                    }
                }
            }
            ++level;
        }
        return -1;
    }
};